package MonotonicStack;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Stack;

/**
 * 获取一个有重复值的数组中每个数左边和
 *
 * @author Liaorun
 */
public class GetFirstLeftAndRightLarger {

    public static void main(String[] args) {
        int[] ints = {2, 5, 3, 4};

        GetFirstLeftAndRightLargerImpl firstLeftAndRightLarger = new GetFirstLeftAndRightLargerImpl(ints);

        System.out.println(firstLeftAndRightLarger.getLeftMax(3));
        System.out.println(firstLeftAndRightLarger.getRightMax(3));
    }

    public static class GetFirstLeftAndRightLargerImpl {

        public int[] arr;
        /**
         * 每个位置的数的左边最大值的位置，K,V均为值的下标索引
         */
        public HashMap<Integer, Integer> leftMax = new HashMap<>();
        /**
         * 每个位置的数的右边最大值的位置，K,V均为值的下标索引
         */
        public HashMap<Integer, Integer> rightMax = new HashMap<>();

        public GetFirstLeftAndRightLargerImpl(int[] arr) {
            this.arr = arr;

            init();
        }

        /**
         * 获取左边比他值大的第一个值的下标
         *
         * @param index 当前值
         * @return 左边有比当前值大 ？ index ： null
         */
        public Integer getLeftMax(int index) {
            return leftMax.get(index);
        }

        /**
         * 获取右边比他值大的第一个值的下标
         *
         * @param index 当前值
         * @return 右边有比当前值大 ？ index ： null
         */
        public Integer getRightMax(int index) {
            return rightMax.get(index);
        }

        private void init() {
            // 单调递减栈
            Stack<ArrayList<Integer>> stack = new Stack<>();

            for (int i = 0; i < arr.length; i++) {
                if (!stack.isEmpty()) {
                    ArrayList<Integer> arrayList = stack.peek();

                    if (arr[arrayList.get(0)] > arr[i]) {
                        // 添加当前数任然是递减栈，直接添加
                        ArrayList<Integer> newOne = new ArrayList<>();
                        newOne.add(i);
                        stack.push(newOne);
                    } else if (arr[arrayList.get(0)] == arr[i]) {
                        arrayList.add(i);
                    } else {
                        // 生成当前弹出的数组的信息
                        ArrayList<Integer> pop = stack.pop();
                        for (Integer index : pop) {
                            rightMax.put(index, i);
                            leftMax.put(index, stack.isEmpty() ? null : stack.peek().get(0));
                        }

                        // 当前数还需要比较
                        i--;
                    }
                } else {
                    // 添加第一个数任然是递减栈，直接添加
                    ArrayList<Integer> newOne = new ArrayList<>();
                    newOne.add(i);
                    stack.push(newOne);
                }
            }

            // 处理最后单调递减栈中的数据
            while (!stack.isEmpty()) {
                ArrayList<Integer> pop = stack.pop();

                for (Integer index : pop) {
                    // 最后剩下的数右侧都没有比它大的值
                    rightMax.put(index, null);
                    leftMax.put(index, stack.isEmpty() ? null : stack.peek().get(0));
                }
            }
        }
    }
}
